Corelab Seminar
2008-2009
Andreas Göbel (NTUA)
On the connection between interval size functions and path counting
Abstract. We investigate the complexity of hard counting problems that belong to the class #P but have easy decision version; several well-known problems such as #PERFECT MATCHINGS, #DNFSAT share this property. We focus on classes of such problems which emerged through two disparate approaches: one taken by Hemaspaandra et al. [HHKW07] who defined classes of functions that count the size of intervals of ordered strings, and one followed by Kiayias et al. [KPSZ98] who defined the class TotP, that consists of functions that count the total number of paths of NP computations and contains #PERFECT MATCHINGS, #DNFSAT as shown by Pagourtzis and Zachos [PZ06]. We provide inclusion and separation relations between TotP and interval size counting classes, by means of new classes that we define in this work. Our results imply that many known #P-complete problems with easy decision are contained in the classes defined in [HHKW07] but are unlikely to be complete for these classes under certain types of reductions. We also define a new class of interval size functions which strictly contains FP and is strictly contained in TotP under reasonable complexity-theoretic assumptions. We show that this new class contains some hard counting problems.
(joint work with E. Bampas, A. Pagourtzis, A. Tentes)